package realization;

import interfaces.BinTree;

import java.io.Console;
import java.util.ArrayList;

public class BinaryTree<T extends Comparable> implements BinTree<T>{

    public Node head;
    private int size;

    private boolean isParent;
    private Node parent;

    private int maxDepth;

    private ArrayList<ArrayList<T>> toOutLevels;
    @Override
    public void insert(T element) {
        if(head == null){
            head = new Node(element,null,null);
            ++size;
            return;
        }
        if(head.insertElement(element))
            ++size;
    }

    @Override
    public boolean delete(T element) {
        Node toDelete = head.findElement(element);
        if(toDelete == null)
            return false;
        if (toDelete == head){
            if(head.left == null && head.right == null){
                head = null;
                --size;
                return true;
            }
            if(head.left == null){
                head = head.right;
                --size;
                return true;
            }
            if(head.right == null){
                head = head.left;
                --size;
                return true;
            }
            T toSet = toDelete.left.rightMost();
            head.data = toSet;

            Node oldBranch = head.left.findElement(toSet);
            if(isParent)
                head.left = oldBranch.left;
            else
                parent.left = oldBranch.left;
        }
        if(toDelete.left == null && toDelete.right == null) {
            if(parent.left != null && parent.left.data.equals(element))
                parent.left = null;
            else
                parent.right = null;
            --size;
            return true;
        }
        if(toDelete.left == null){
            if(parent.left != null && parent.left.data.equals(element))
                parent.left = toDelete.right;
            else
                parent.right = toDelete.right;
            --size;
            return true;
        }
        if(toDelete.right == null){
            if(parent.left != null && parent.left.data.equals(element))
                parent.left = toDelete.left;
            else
                parent.right = toDelete.left;
            --size;
            return true;
        }
        T toSet = toDelete.left.rightMost();
        toDelete.data = toSet;

        Node oldBranch = toDelete.left.findElement(toSet);
        if(isParent)
            toDelete.left = oldBranch.left;
        else
            parent.left = oldBranch.left;
        --size;
        return true;
    }

    @Override
    public boolean isExist(T element) {
        if(head == null)
            return false;
        return head.findElement(element)!= null;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void deleteAll() {
        head = null;
        size = 0;
    }

    @Override
    public void printAllLevels() {
        toOutLevels = new ArrayList<ArrayList<T>>();
        maxDepth = depth(head);
        for(int i = 0; i < maxDepth; ++i)
            toOutLevels.add(new ArrayList<T>());
        addLevel(head,0);
        int counterShl = maxDepth;
        for(int i = 0; i < toOutLevels.size(); ++i){
            for (int j = i+1; j < counterShl*5; ++j)
                System.out.printf("%-1s","");
            for(T elem : toOutLevels.get(i)){
                System.out.printf("%-5s",(elem != null? elem : "_"));
                for (int j = 0; j < counterShl; ++j)
                    System.out.printf("%-5s","");
            }
            counterShl>>=1;
            System.out.println();
        }
    }

    private void addLevel(Node nodeToAdd, int depth){
        if(depth >= maxDepth)
            return;
        toOutLevels.get(depth).add(nodeToAdd != null?nodeToAdd.data:null);
        addLevel(nodeToAdd != null?nodeToAdd.left : null, depth + 1);
        addLevel(nodeToAdd != null?nodeToAdd.right : null, depth + 1);
    }

    public int depth(Node toCalculate){
        if(toCalculate == null)
            return 0;
        int left = depth(toCalculate.left);
        int right = depth(toCalculate.right);
        return 1 + (left > right ? left : right);
    }

    @Override
    public void printAllDepth() {
        //To change body of implemented methods use File | Settings | File Templates.
    }

    private class Node
    {
        public T data;
        public Node left;
        public Node right;

        public Node(T data, Node left, Node right)
        {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public boolean insertElement(T element){
            int compareResult = element.compareTo(data);
            if(compareResult < 0){
                if(left==null)
                    left = new Node(element,null,null);
                else
                    left.insertElement(element);
                return true;
            }else if(compareResult > 0){
                if(right==null)
                    right = new Node(element,null,null);
                else
                    right.insertElement(element);
                return true;
            }
            return false;
        }

        public T rightMost(){
            Node currentNode = this;
            while (currentNode.right != null)
                currentNode = currentNode.right;
            return currentNode.data;
        }

        public Node findElement(T element){
            int resultCompare = element.compareTo(data);
            if(resultCompare < 0){
                if(this.left == null)
                    return null;
                Node toReturn = this.left.findElement(element);
                if(isParent){
                    parent = this;
                    isParent = false;
                }
                return toReturn;
            }else if(resultCompare > 0){
                if(this.right == null)
                    return null;
                Node toReturn = this.right.findElement(element);
                if(isParent){
                    parent = this;
                    isParent = false;
                }
                return toReturn;
            }
            isParent = true;
            return this;
        }
    }
}
